The present invention relates to the field of image processing, and more particularly to a method and apparatus for image compression.
Modern computer systems are often required to transmit large amounts of image data across relatively low bandwidth communication channels. Consequently, to reduce the amount of bandwidth consumed per image transmission, images are often compressed using one of a number of compression techniques.
In one image compression technique, called xe2x80x9cvector quantizationxe2x80x9d, digitized imaged are resolved into small blocks of pixels represented by vectors. Vectors are values that convey color and intensity information. For example, a common type of vector is an RGB vector (i.e., red, green, blue) that indicates the average intensities of red, green and blue colors in a pixel block. In a vector quantization system, each vector of an image is replaced by an index to a table called a codebook. A codebook is a table containing a relatively small number of vectors that can be used to represent vectors in an input image. For each vector in the input image, the codebook is searched to find a representative vector and the address of the representative vector, i.e., a code book index, is transmitted in place of the input vector. Because the codebook indices are smaller than the image vectors, substituting the indices for the image vectors effectively compresses the representation of the image and reduces the bandwidth required to transmit the image. In a receiving device, the codebook indices are used to look up representative vectors in another codebook that is the same as or similar to the codebook used to compress the original image. The representative vectors are then used to construct an output image.
FIG. 1 is a block diagram of a prior art system that performs vector quantization. The system includes an encoder 11 that encodes (i.e., compresses) an input image 12, then transmits the encoded image to a decoder 21. The decoder 21 decodes the encoded image to generate an output image 26. In many cases, the encoder 11 and the decoder 21 are realized by computers programmed to implement corresponding compression and decompression algorithms.
The encoder 11 typically contains a preprocessor 16, a vector quantizer 18, a codebook 17 and a transmitter 19. The preprocessor 16 is used to reduce the amount of image data that is processed by the vector quantizer 18, for example, by filtering high frequency components from the input image 12. The preprocessed image is supplied to the vector quantizer 18 which identifies representative vectors in the codebook 17 that, by some measure, are a best match for vectors in the preprocessed image. Because the codebook 23 in the decoder 21 is typically the same as or similar to the codebook 17 in the encoder 11, addresses of the representative vectors in the codebook 17, i.e., codebook indices, may be transmitted to the decoder 21 and used to look up the representative vectors in the codebook 23. The representative vectors are then used to generate the output image 26. In some implementations, a post processor 25 may perform additional processing (e.g., pixel-block up-sampling, dithering, etc.) to produce the output image 26.
Because the number of representative vectors in the codebook 17 is usually small relative to the total number of possible input vectors, the bit size of each codebook index is correspondingly smaller than the bit size of the input vectors. For example, if each input vector is a 24-bit value (e.g., a xe2x80x9ctrue colorxe2x80x9d value in which red, green and blue intensities are each represented by a respective one of three bytes) and the codebooks (17 and 23) each contain 256 representative vectors, then a one-byte codebook index can be used to represent each of the three-byte input vectors. This is a 3:1 reduction of the amount of data used to represent the preprocessed image.
One disadvantage of the above-described image compression technique is that the overall compression that can be achieved is limited by the vector-based approach. More specifically, because input images are decomposed into pixel blocks for vector quantization, patterns within the images that could otherwise be exploited for compression purposes may not be recognized. As a result, the overall compression achieved by the above described compression technique may be less than the compression possible with a non-vector-based approach.
A method and apparatus for compressing a digitized image are disclosed. Boundaries of regions within a digitized image are identified and shapes are selected from a bank of shapes to represent the regions based on the identified boundaries. Position and size information is associated with the selected shapes based on the position and size of the regions within the digitized image. Values indicating the selected shapes and the associated position and size information are transmitted as a representation of the digitized image.
Other features and advantages of the invention will be apparent from the accompanying drawings and from the detailed description that follows below.